Course contents: Algorithms and computational problems, Analysis of algorithms, Asymptotic notations, Recurrence relations. Design techniques: Divide-and-Conquer, Greedy algorithms, Dynamic programming. Graph algorithms: Breadth first search, Depth first search, Topological sorting, Minimum spanning trees, Shortest paths. Introduction to complexity theory: P, NP, and NP-complete problems, Polynomialtime reductions. Special topics: Approximation algorithms, Randomized algorithms and Computational geometry.

At the end of the course the student will be able to:

• describe algorithms for a series of classical computational problems and show their execution on typical instances.
• apply algorithm design techniques and construct efficient algorithms.
• describe algorithms with clarity in words and in pseudocode.
• analyze the complexity of an algorithm and prove its correctness.
• recognize basic notions of NP-completeness theory.

Assessment: Assignments with weight 30%-40% and written exam.